package com.nine.algorithm.leetcode.list;

/**
 * @author nine
 * @version 1.0
 * @description 删除链表倒数第N个节点
 * @date 24/5/4 18:47
 */
public class Leetcode019 {

	/**
	 * 方法一：递归方式实现
	 *
	 * @param head 链表
	 * @param n    倒数第N个
	 * @return
	 */
	public static ListNode removeNthFromEnd(ListNode head, int n) {
		// 使用链表哨兵
		ListNode s = new ListNode(-1, head);
		recursion(s, n);
		// 哨兵的话，删除s.next
		return s.next;
	}

	/**
	 * 先递归，查询每次递归过来的位置
	 *
	 * @param p 链表
	 * @param n 倒数的位置
	 * @return
	 */
	public static int recursion(ListNode p, int n) {
		if (p == null) {
			return 0;
		}
		// 下一个节点的倒数位置
		int nth = recursion(p.next, n);
		System.out.print("--" + (p.val + ":" + (nth + 1)));
		if (nth == n) {
			p.next = p.next.next;
		}
		return nth + 1;
	}

	/**
	 * 方法二：双指针，中间隔n个元素
	 *
	 * @param head
	 * @param n
	 * @return
	 */
	public static ListNode removeNthFromEnd2(ListNode head, int n) {
		// 添加哨兵节点
		ListNode s = new ListNode(-1, head);

		// 双指针，指针之间隔 n 个元素
		ListNode p1 = s;
		ListNode p2 = s;

		// n+1：最后一个元素为null
		for (int i = 0; i < n + 1; i++) {
			p2 = p2.next;
		}
		while (p2 != null) {
			p1 = p1.next;
			p2 = p2.next;
		}
		p1.next = p1.next.next;
		return s.next;
	}


	public static void main(String[] args) {
		ListNode head = ListNode.of(1, 2, 6, 3, 4, 5, 6);
		System.out.println("初始链表：" + head);
		// ListNode listNode = removeNthFromEnd(head, 7);
		ListNode listNode = removeNthFromEnd2(head, 2);
		System.out.println();
		System.out.println("listNode = " + listNode);
	}

}
